//前 n 个数字二进制中 1 的个数
class Solution {
public:
    vector<int> countBits(int n) 
    {
        vector<int>res;
        int flag=1;
        for(int i=0;i<=n;i++)
        {
            int num=0;
            for(int j=0;j<32;j++)
            {
                if((flag<<j)&i)
                {
                    num++;
                }
            }
            res.push_back(num);
        }
        return res;
    }
};

//二进制加法
class Solution {
public:
    string addBinary(string a, string b) 
    {
        string res;
        int i=a.size()-1;
        int j=b.size()-1;
        int carry=0;
        while(i >=0 || j>=0)
        {
            int na= i>=0? a[i]-'0':0;
            int nb= j>=0? b[j]-'0':0;
            int sum=na+nb+carry;
            res.push_back((sum%2)?'1':'0');
            carry=sum/2;
            i--,j--;
        }
        if(carry)
        {
            res.push_back('1');
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

//含有重复元素集合的组合

class Solution {
public:
    vector<vector<int>>res;
    vector<int>tmp;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        if(candidates.empty()) return res;
        sort(candidates.begin(),candidates.end());
        vector<bool>used(candidates.size(),false);
        dfs(candidates,used,target,0,0);
        return res;
    }
    void dfs(vector<int>& candidates , vector<bool>& used,int target,int sum,int curi)
    {
        if(sum>=target)
        {
            if(sum==target)
            {
                res.push_back(tmp);
            }
            return;
        }
        for(int i=curi;i<candidates.size();i++)
        {
            if(i>0 && candidates[i]==candidates[i-1] && !used[i-1]) continue;
            else
            {
                used[i]=true;
                tmp.push_back(candidates[i]);
                dfs(candidates,used,target,sum+candidates[i],i+1);
                used[i]=false;
                tmp.pop_back();
            }
        }
    }

};

//没有重复元素集合的全排列
class Solution {
public:
    vector<int>tmp;
    vector<vector<int>> res;
    vector<vector<int>> permute(vector<int>& nums) 
    {
        vector<bool>used(nums.size(),false);
        dfs(nums,used);
        return res;
    }
    void dfs(vector<int>& nums,vector<bool>& used)
    {
        if(tmp.size()==nums.size())
        {
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(used[i]) continue;
            used[i]=true;
            tmp.push_back(nums[i]);
            dfs(nums,used);
            used[i]=false;
            tmp.pop_back();
        }
    }
};
//含有重复元素集合的全排列
class Solution {
public:
    vector<int>tmp;
    vector<vector<int>>res;
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        if(nums.empty()) return res;
        sort(nums.begin(),nums.end());
        vector<bool>used(nums.size(),false);
        dfs(nums,used);
        return res;
    }
    void dfs(vector<int>&nums,vector<bool>&used)
    {
        if(tmp.size()==nums.size())
        {
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<nums.size();i++)
        {
            
            if(i>0 && nums[i]==nums[i-1] && !used[i-1]) continue;
            if(used[i]) continue;
            used[i]=true;
            tmp.push_back(nums[i]);
            dfs(nums,used);
            used[i]=false;
            tmp.pop_back();
        }

    }
};

//生成匹配的括号
class Solution {
public:
    string tmp;
    vector<string> res;
    vector<string> generateParenthesis(int n) 
    {
        dfs(n,0,0);
        return res;
    }
    void dfs(int n,int lsize,int rsize)
    {
        if(rsize==n)
        {
            res.push_back(tmp);
            return;
        }
        if(lsize<n)
        {
            tmp.push_back('(');
            dfs(n,lsize+1,rsize);
            tmp.pop_back();
        }
        if(rsize<lsize)
        {
            tmp.push_back(')');
            dfs(n,lsize,rsize+1);
            tmp.pop_back();
        }

    }
};

//单词长度的最大乘积
class Solution {
public:
    int maxProduct(vector<string>& words) 
    {
        //不用字符串哈希 用二进制哈希
        //用一个int类型 来存26个英文字母绰绰有余
        vector<int>mask(words.size());

        for(int i=0;i<words.size();i++)
        {
            string word=words[i];
            //word = abcd
            for(int j=0;j<word.size();j++)
            {
                //出现什么字母就把那一位字母置1
                mask[i] |= 1<<(word[j]-'a');
            }
        }
        int res=0;
        for(int i=0;i<words.size();i++)
        {
            for(int j=i+1;j<words.size();j++)
            {
                if((mask[i] & mask[j] )==0)
                {
                    res=max(res,int(words[i].size()*words[j].size()));
                }
            }
        }
        return res;
    }
};


//只出现一次的数字
class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int res=0;
        for(int i=0;i<32;i++)
        {
            int times=0;
            for(int j=0;j<nums.size();j++)
            {
                if( (1<<i) & nums[j])
                {
                    //当前位有值
                    times++;
                }
                //没值不管
            }
            if(times%3)
            {
                res|=(1<<i);
            }
        }
        return res;
    }
};